package com.cjl.interview150.arrayAndString;

import org.junit.jupiter.api.Test;

import java.util.*;


public class ArrayStringPractice {
    /**
     * 88. 合并两个有序数组
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 定义三个指针
        int len1 = m - 1;
        int len2 = n - 1;
        int len = m + n - 1;
        while (len1 >= 0 && len2 >= 0) {
            /*if (nums1[len1] > nums2[len2]) {
                nums1[len] = nums1[len1];
                len1--;
            } else {
                nums1[len] = nums2[len2];
                len2--;
            }
            len--;*/
            nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
        }
        // 将num2从0到len2 - 1的元素拷贝到num10的位置
        System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
    }

    /**
     * 27. 移除元素 双指针法
     *
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }

    /**
     * 26. 删除有序数组中的重复项
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        // 双指针法
        // 慢指针在第一项
        int slow = 0;
        // 快指针在循环中初始化为第二项
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[slow] != nums[fast]) {
                nums[slow + 1] = nums[fast];
                slow++;
            }
        }
        return slow + 1;
    }

    /**
     * 80. 删除有序数组中的重复项 II
     *
     * @param nums
     * @return
     */
    public int removeDuplicates2(int[] nums) {
        // 双指针法
        // 慢指针在第一项
        int slow = 0;
        // 快指针在循环中初始化为第二项
        for (int fast = 2; fast < nums.length; fast++) {
            if (nums[slow] != nums[fast]) {
                nums[slow + 2] = nums[fast];
                slow++;
            }
        }
        return slow + 2;
    }

    /**
     * 169. 多数元素
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        // key: 元素 value:出现次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        int len = nums.length;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer value = entry.getValue();
            if (value > len / 2) {
                return entry.getKey();
            }
        }
        return 0;
    }

    /**
     * 189. 轮转数组
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        // 1.反转整个数组
        reverse(nums, 0, nums.length - 1);
        // 2.从k分割两个数组，并别分反转
        k %= nums.length;
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    /**
     * 274. H 指数
     *
     * @param citations
     * @return
     */
    public int hIndex(int[] citations) {
        // 获取数组长度
        int n = citations.length;
        // 对数组进行排序
        Arrays.sort(citations);
        // 定义h为n
        int h = n;
        while (h > 0) {
            // 一旦发现citations[n - h] >= h则说明后面的一定也大于等于h，则h就是该作者的h指数
            if (citations[n - h] >= h) {
                return h;
            }
            h--;
        }
        return h;
    }

    /**
     * 238. 除自身以外数组的乘积
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        // 初始化辅助变量
        res[0] = 1;
        int temp = 1;
        // 计算下三角
        for (int i = 1; i < len; i++) {
            // 每次和上
            res[i] = res[i - 1] * nums[i - 1];
        }
        // 计算上三角
        for (int i = len - 2; i >= 0; i--) {
            temp = temp * nums[i + 1];
            res[i] = temp * res[i];
        }
        return res;
    }

    /**
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        /**
         分两个阶段
         1、起点下标1从左往右，只要右边比左边大，右边的糖果=左边 + 1
         2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，
         此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1
         二者的最大值，这样才符合 它比它左边的大，也比它右边大
         */
        // 糖果数组
        int len = ratings.length;
        int[] candyNum = new int[len];
        // 第一项初始化为1
        candyNum[0] = 1;
        // 从左往右遍历,如果右边评分比左大,则 右 = 左 + 1,否则就为1
        for (int i = 1; i < len; i++) {
            candyNum[i] = ratings[i] > ratings[i - 1] ? candyNum[i - 1] + 1 : 1;
        }
        // 从右往左遍历,如果左边比右边大,则candyNum[i]取其本身和candyNum[i + 1]
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyNum[i] = Math.max(candyNum[i + 1] + 1, candyNum[i]);
            }
        }
        return Arrays.stream(candyNum).sum();
    }

    /**
     * 13. 罗马数字转整数
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     *
     * @param s
     * @return
     */
    public int romanToInt(String s) {
        int sum = 0;
        int preNum = getNum(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int curNum = getNum(s.charAt(i));
            if (curNum > preNum) { // 如果当前这位比上一位小则直接加
                sum -= preNum;
            } else {
                sum += preNum;
            }
            // 重置上一位的数字方便下次循环
            preNum = curNum;
        }
        sum += preNum;
        return sum;
    }

    private int getNum(char c) {
        switch (c) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }

    /**
     * 12. 整数转罗马数字
     *
     * @param num
     * @return
     */
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < values.length; i++) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                sb.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return sb.toString();
    }

    /**
     * 58. 最后一个单词的长度
     * @param s
     * @return
     */
    public int lengthOfLastWord(String s) {
        String[] arr = s.split(" ");
        return arr[arr.length - 1].length();

    }

    /**
     * 14. 最长公共前缀
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串数组为空则直接返回空字符串
        if (strs.length == 0) {
            return "";
        }
        // 取第一个字符串为比较对象
        String res = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < res.length() && j < strs[i].length(); j++) {
                // 此时公共前缀不相等
                if (res.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            // 截取当前循环的公共前缀
            res = res.substring(0, j);
            // 如果已经为空则直接返回
            if (res.equals("")) {
                return res;
            }
        }
        return res;
    }

    /**
     * 6. N 字形变换
     * @param s 原始字符串
     * @param numRows 转变的行数
     * @return 转变之后的字符串
     */
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        ArrayList<StringBuilder> list = new ArrayList<>();
        // 当前遍历的行
        int index = 0;
        // 遍历方向
        int direction = -1;
        // 创建每一行的字符串
        for (int i = 0; i < numRows; i++) {
            list.add(new StringBuilder());
        }
        // 开始遍历填充
        for (char c : s.toCharArray()) {
            list.get(index).append(c);
            // 判断是否到转折点
            if (index == 0 || index == numRows - 1) {
                direction = -direction;
            }
            // 找下一个指定行插入字符
            index += direction;
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder sb : list) {
            res.append(sb);
        }
        return res.toString();
    }
}

/**
 * 380. O(1) 时间插入、删除和获取随机元素
 */
class RandomizedSet {
    private ArrayList<Integer> list;
    private HashMap<Integer, Integer> map;
    private Random r;


    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        r = new Random();
    }

    public boolean insert(int val) {
        // 通过map判断集合中是否有这个数
        if (map.containsKey(val)) {
            return false;
        }
        // 获取list长度
        int index = list.size();
        // 插入val
        list.add(val);
        // 通过map记录val和下标
        map.put(val, index);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        // 获取val的下标
        Integer index = map.get(val);
        // 用最后一位覆盖val
        Integer last = list.get(list.size() - 1);
        // 更新list和map
        list.set(index, last);
        map.put(last, index);
        // 删除list和map中的信息
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        int index = r.nextInt(list.size());
        return list.get(index);
    }
}

